#include<bits/stdc++.h>
using namespace std;
int n,T;
string f[15],t;
bool check(int x){
	for(int i=0;i<t.size();i++){
		if(x+i>=f[n].size())return 0;
		if(f[n][x+i]!=t[i])return 0;
	}
	return 1;
}
void w(){
	int res=0;
	for(int i=0;i<f[n].size();i++){
		res+=check(i);
	}
	cout<<res<<endl;
	return;
}
signed main(){
	freopen("brotherhood.in","r",stdin);
	freopen("brotherhood.out","w",stdout);
	cin>>n>>T;
	f[1]="0";
	f[2]="1";
	for(int i=3;i<=n;i++)f[i]=f[i-1]+f[i-2];
	for(int i=1;i<=T;i++){
		t.clear();
		cin>>t;
		w(); 
	}
	return 0;
} 
